package leetcode.code1017;

import leetcode.helper.H;

public class Solution1 {
	public String baseNeg2(int n) {
		if(n == 0) {
			return "0";
		}
		int[] bits = new int[32];
		for (int i = 0; i < 32 && n != 0; i++, n >>= 1) {
			bits[i] += n & 1;
			if ((n & 1) == 1 && (i & 1) == 1) {
				bits[i + 1] += 1;
			}
		}
		StringBuffer ans = new StringBuffer();
		int carry = 0;
		for (int i = 0; i < 32; i++) {
			int sum = carry + bits[i];
			int cur = sum & 1;
			carry = (sum - cur) / -2;
			ans.append(cur);
		}
		int p = ans.length();
		while (ans.charAt(p - 1) == '0') {
			p--;
		}
		return ans.reverse().substring(ans.length() - p);
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		H.print(so.baseNeg2(1));
		H.print(so.baseNeg2(0));
		H.print(so.baseNeg2(2));
		H.print(so.baseNeg2(3));
		H.print(so.baseNeg2(4));
	}
}
